package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/4 11:45
 * @DESCRIPTION
 */
// 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
// 只使用数字1到9
// 每个数字 最多使用一次
// 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
public class 组合总和3 {
    //自己写出，和组合解法几乎一样
    LinkedList<Integer> path=new LinkedList<>();
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> method1(int k, int n) {
        recursion(1,k,n);
        return res;
    }

    public void recursion(int head,int k, int n){
        if(k<=0){
            if(n==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        //i <=9-(k-1)是进行剪枝操作，如果剩下的数少于k-1个，根本不可能有正确解，因此直接跳过
        for (int i = head; i <=9-(k-1); i++) {
            path.add(i);
            recursion(i+1,k-1,n-i);
            path.removeLast();
        }
    }

    public List<List<Integer>> practice(int k, int n) {
        recursionPractice(k,n,1);
        return res;
    }

    public void recursionPractice(int k,int n,int startIndex){
        if(k==0||n<=0){
            if(k==0&&n==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <=9 ; i++) {
            path.add(i);
            recursionPractice(k-1,n-i,i+1);
            path.removeLast();
        }
    }
}
